/*
题目：反转链表Ⅱ
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class ReverseBetween {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode ret = new ListNode(0, head);
        ListNode cur = head;
        int i = 1;
        ListNode first = ret;   //记录left左边第一个节点的位置
        while (i < left) {
            i++;
            first = cur;
            cur = cur.next;
        }
        ListNode second = cur;//再记录Left当前位置的节点
        ListNode prev = null;
        while (i <= right) {
            i++;
            ListNode front = cur.next;
            cur.next = prev;
            prev = cur;
            cur = front;
        }
        first.next = prev;   //重新连接这两个部分
        second.next = cur;
        return ret.next;
    }
}
